package 题目集.动态规划.背包问题;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

/**
 * https://www.luogu.com.cn/problem/P1757 设i组的物品有a1,a2..an。每组背包只能选一件，最后能拿到的最大值
 * dp[i][j]：有i组可选时，容量为j的最大值。
 * dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[a1]]+v[a1],dp[i-1][j-w[a2]]+v[a2].......,dp[i-1][j-w[an]]+v[an]);
 */
public class ch06_分组背包 {
	static int[][] info;
	static int maxK = 101;
	static int n, sum, cnt;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		sum = sc.nextInt();
		n = sc.nextInt();
		info = new int[n + 1][3];
		Set<Integer> set = new HashSet<>();
		for (int i = 1; i <= n; i++) {
			info[i][0] = sc.nextInt();
			info[i][1] = sc.nextInt();
			info[i][2] = sc.nextInt();
			set.add(info[i][2]);
		}
		cnt = set.size(); // 组的个数
		Arrays.sort(info, (a, b) -> a[2] - b[2]); // 让相同组的凑到一块
		int res = dp(cnt, sum);
		System.out.println(res);
	}

	public static int dp(int n, int sum) {
		int[][] dp = new int[2][sum + 1];
		int pre, cur = 0;
		// s是这组开始的位置
		for (int i = 1, s = 1; s < info.length && i <= n; i++) {
			pre = cur;
			cur = (cur + 1) % 2;
			int end = s + 1;
			// 找到当前组结束位置,可二分
			while (end < info.length && info[end][2] == info[s][2])
				end++;
			for (int j = 0; j <= sum; j++) {
				dp[cur][j] = dp[pre][j];
				for (int k = s; k < end; k++) {
					if (j >= info[k][0]) {
						dp[cur][j] = Math.max(dp[cur][j], dp[pre][j - info[k][0]] + info[k][1]);
					}
				}
			}
			s = end;
		}
		return dp[cur][sum];
	}
}
